package cc.ccoke.algorithms.primary.chapter01;

import cc.ccoke.algorithms.util.ArrayUtils;

/**
 * 小和问题(使用归并排序解决)
 * 在一个数组中，每一个左边比当前数小的数累加起来，叫做这个数组的小和
 * @author ccoke
 */
public class SmallSum {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateByInt(10, 20);
        ArrayUtils.print(arr);
        System.out.println("--- small sum ---");
        System.out.println(getSmallSum(arr, 0, arr.length - 1));
    }

    private static int getSmallSum(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int middle = (left + right) / 2;
        int leftSum = getSmallSum(arr, left, middle);
        int rightSum = getSmallSum(arr, middle + 1, right);
        return leftSum + rightSum + merge(arr, left, middle, right);
    }

    private static int merge(int[] arr, int left, int middle, int right) {
        int[] temp = new int[right - left + 1];
        int p = left;
        int q = middle + 1;
        int sum = 0;
        int index = 0;
        while (p <= middle && q <= right) {
            sum += arr[p] < arr[q] ? (right - q + 1) * arr[p] : 0;
            temp[index++] = arr[p] < arr[q] ? arr[p++] : arr[q++];
        }
        //右数组是否有剩余
        while (p <= middle) {
            temp[index++] = arr[p++];
        }
        //左数组是否有剩余
        while (q <= right) {
            temp[index++] = arr[q++];
        }
        // 改变原数组对应位置
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
        return sum;
    }


}
